리스트

리스트(List)는 말 그대로 순서대로 저장하는 시퀸스이자 변경 가능한 목록(Mutable List)이다.

특징은 다음과 같다.

• 입력 순서가 유지된다.

  • 연속된 공간에 요소를 배치하는 배열의 장점과 다양한 타입을 연결해 배치하는 연결 리스트의 장점을 모두 취한 듯한 형태이다.

• 파이썬은 모든 것이 객체이며 리스트 또한 마찮가지이다.

  • 연결 리스트에 대한 포인터 목록을 배열 형태로 관리한다.
  • 자료형의 크기는 저마다 서로 다르기 때문에 이들을 연속된 메모리 공간에 할당하는 것은 불가능하다.

• 내부적으로는 동적 배열로 구현되어 있다.

  • C에서는 vector, 자바는 ArrayList 와 같다.
• 리스트 자료형을 이용하면 스택, 큐를 한번에 구현이 가능하다.

[리스트의 주요 연산 시간 복잡도]

리스트의 경우 탐색 시 값의 존재 유무를 확인하려면 정렬된 경우에는 이진 검색이 효율적이다.

존재하지 않는 인덱스를 조회할 경우 IndexError가 발생한다.

리스트에서 요소 삭제하기

• 인덱스로 삭제하기

  • del 키워드를 사용하면 인덱스로 삭제가 가능하다. ex) del a[1]

• 값으로 삭제하기

  • remove() 함수를 사용하면 값에 해당하는 요소를 삭제할 수 있다. ex) a.remove(3)

딕셔너리

내부적으로는 해시 테이블(Hash Table)로 구현되어 있다. 해시할 수만 있다면 숫자 뿐만 아니라, 문자, 집합까지 불변 객체를 모두 키로 사용할 수 있다. 이 과정을 해싱이라고 하며, 해시 테이블을 이용해 자료를 저장한다. 또한 입력과 조회 모두 O(1)에 가능하다는 특징이 있다.

[딕셔너리의 주요 연산 시간 복잡도]

기존에 딕셔너리는 입력 순서가 유지되지 않았지만 파이썬 3.6 이하에서는 collections.OrderedDict() 라는 별도 자료형을 제공했었다. 그러나 3.7부터는 내부적으로 인덱스를 이용해 입력 순서를 유지한다.

또한 조회 시 항상 디폴트 값을 생성해 키 오류를 방지하는 collections.defaultdict(),

요소의 값을 키로 하고 개수를 값 형태로 만들어 카운팅 하는 collections.Counter() 등이 있다.

딕셔너리에서는 존재하지 않는 키를 조회하면 KeyError 에러가 발생한다.

에러처리 방법

• try, except

del a['key4']
try:
    print(a['key4'])
except KeyError:
	print('존재하지 않는 키')

• if 문을 통한 키값을 확인

'key4' in a
>> Fasle

if 'key4' in a:
	print('존재하는 키')
else:
	print('존재하지 않는 키')

또한 키/값을 for 반복문으로도 조회가 가능하다.

for k, v in a.items():
	print(k, v)

defaultdict 객체

a = collections.defaultdict(int)
a['A'] = 5
a['B'] = 4
>>> a
defaultdict(<class 'int'>, {'A': 5, 'B': 4})
# C라는 키는 존재하지 않는다.
a['C'] += 1
>>> a
defaultdict(<class 'int'>, {'A': 5, 'B': 4,'C': 1})

원래라면 C 키 값에 +1를 해주면 KeyError가 발생했겠지만 에러 없이 자동으로 디폴트인 0을 기준으로 자동 생성한 후 여기에 1을 더해줬다.

Counter 객체

>>> a = [1, 2, 3, 4, 5, 5, 5, 6, 6]
>>> b = collections.Counter(a)
>>> b
Counter({5: 3, 6:2, 1:1, 2: 1, 3: 1, 4: 1})

가장 빈도 수가 높은 요소는 most_common()을 사용하면 된다.

b.most_common(2) = [(5, 3), (6, 2)]